/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package edu.tue.nl.aa;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

/**
 * Notes from Lecture 5:
 * Suppose we are given a collection of n jobs that must be executed. To execute the jobs we
 * have m identical machines, M1, ... , Mm , available. Executing job t on any of the machines
 * takes time tj , where tj>0. Our goal is to assign the jobs to the machines in such a way that
 * the so-called makespan, the time until all jobs are finished, is as small as possible. Thus we
 * want to spread the jobs over the machines as evenly as possible. Hence, we call this problem
 * Load Balancing.
 * Let’s denote the collection of jobs assigned to machine Mi by A(i). Then the load Ti of
 * machine Mi —the total time for which Mi is busy—is given by:
 *                          Ti = sum( tj ), where t is member of A(i).
 * and the makespan of the assignment is the maximum Ti, from machine Mi.
 * The Load Balancing problem is to find an assignment of jobs to machines that
 * minimizes the makespan, where each job is assigned to a single machine.
 * (We cannot, for instance, execute part of a job on one machine and the rest of the job on a
 * different machine.) Load Balancing is NP-hard. Our first approximation algorithm for
 * Load Balancing is a straightforward greedy al-gorithm:
 * we consider the jobs one by one and assign each job to the machine whose current
 * load is smallest.
 * A weak point of our greedy algorithm is the following. Suppose we first have a large number
 * of small jobs and then finally a single very large job. Our algorithm will first spread the small
 * jobs evenly over all machines and then add the large job to one of these machines. It would
 * have been better, however, to give the large job its own machine and spread the small jobs over
 * the remaining machines. Note that our algorithm would have produced this assignment if the
 * large job would have been handled first. This observation suggest the following adaptation
 * of the greedy algorithm: we first sort the jobs according to decreasing processing times, and
 * then run Greedy-Scheduling. We call the new algorithm Ordered-Scheduling.
 * Does the new algorithm really have a better approximation ratio? The answer is yes.
 * The Algorithm Ordered-Scheduling is a (3/2)-approximation algorithm.
 * 
 * @author waldo
 */
public class OrderedSchedulingAlgorithm {

    private ArrayList<MachineDTO> m;
    private ArrayList<JobDTO> t;
    
    /**
     * Constructor.
     * @param nMachines , amount of machines. Must be 2 at least.
     * @param t , list of jobs.
     */
    public OrderedSchedulingAlgorithm( ArrayList<JobDTO> t, int nMachines ) throws Exception{
        if( nMachines<2 || t.isEmpty() )
            throw new java.lang.Exception("At least two required machines and a non-empty jobs array.");
        this.t = t;
        m = new ArrayList<MachineDTO>();
        for( int i=0;i<nMachines;i++ ) m.add(new MachineDTO());
    }

    /**
     * Implementation of Comparator, designed to order the jobs.
     */
    private class JobComparator implements Comparator<JobDTO>{
        @Override public int compare(JobDTO j1, JobDTO j2) {
            if( j1.getTime()<j2.getTime() ) return 1;
            else if( j1.getTime()>j2.getTime() ) return -1;
            else return 0;
        }   
    }
    /**
     * Implementation of Comparator, designed to get the machine with minimum load.
     */
    private class MachineTotalJobTimeComparator implements Comparator<MachineDTO>{
        @Override public int compare(MachineDTO m1, MachineDTO m2) {
            if( m1.getTimeLoad()<m2.getTimeLoad() ) return -1;
            else if( m1.getTimeLoad()>m2.getTimeLoad() ) return 1;
            else return 0;
        }
    }

    /**
     * Ordered-Scheduling(t1, ... , tn, m)
     * 0. Order jobs.
     * 1. Initialize Ti ← 0 and A(i) ← ∅ for 1<=i<=m.
     * 2. for j ← 1 to n
     * 3.   do Assign job t to the machine Mk of minimum load
     * 4.      Find a k such that Tk = min(1<=i<=m,Ti)
     * 5.      A(k) ← A(k) ∪ {t}; Tk ← Tk + tj
     * @param doOrderedScheduling , true implies to use ordered scheduling.
     */
    public void doGreedyScheduling( boolean doOrderedScheduling ){
        MachineTotalJobTimeComparator mc = new MachineTotalJobTimeComparator();
        // (0)
        JobDTO job;
        if( doOrderedScheduling ){
            JobComparator jc = new JobComparator();
            Collections.sort(t,jc);
        }
        // (1) (Done in the constructor)
        // (2)
        for( int j=0; j<t.size(); j++ ){
            job = t.get(j);
            //(3).(4).(5)
            Collections.sort(m, mc);
            m.get(0).addJob(job);
        }
    }
    
    /**
     * @return 
     */
    public ArrayList<MachineDTO> getResult(){ return m; }
    /**
     * @return 
     */
    public ArrayList<JobDTO> getJobs(){ return t; }

}
